package com.javabasic.algorithm.leetcode;

import java.util.Random;

/**
 * @author mir.xiong
 * @version 1.0
 * @description
 * @link [497. 非重叠矩形中的随机点 - 力扣（LeetCode）](https://leetcode.cn/problems/random-point-in-non-overlapping-rectangles/)
 * @see
 * @since Created by work on 2022/6/9 22:20
 */
public class RandomPointInNonOverlappingRectangles {

}

/**
 * 超出内存限制
 */
class Solution {

    private int[][] nums;
    private Random random;
    private int size;

    public Solution(int[][] rects) {
        int len = rects.length;
        int size = 0;
        for (int i = 0; i < len; i++) {
            int p1x = rects[i][0];
            int p1y = rects[i][1];
            int p2x = rects[i][2];
            int p2y = rects[i][3];
            size += ((Math.abs(p1x - p2x) + 1) * (Math.abs(p1y - p2y) + 1));
        }

        System.out.println(size);

        nums = new int[size][2];

        int index = 0;
        for (int i = 0; i < len; i++) {
            int p1x = rects[i][0];
            int p1y = rects[i][1];
            int p2x = rects[i][2];
            int p2y = rects[i][3];

            for (int j = p1x; j <= p2x; j++) {
                for (int k = p1y; k <= p2y; k++) {
                    nums[index][0] = j;
                    nums[index][1] = k;
                    index++;
                }
            }
        }

        random = new Random(size);
        this.size = size;
    }

    public int[] pick() {
        int index = random.nextInt(size);
        return nums[index];
    }
}


/**
 * 超出内存限制
 */
class Solution2 {

    private int[] nums;
    private int len;
    private Random random;
    private int points;
    private int[][] rects;

    public Solution2(int[][] rects) {
        this.rects = rects;
        len = rects.length;
        nums = new int[len];
        points = 0;
        int index = 0;
        for (int i = 0; i < len; i++) {
            int p1x = rects[i][0];
            int p1y = rects[i][1];
            int p2x = rects[i][2];
            int p2y = rects[i][3];
            nums[index] = ((Math.abs(p1x - p2x) + 1) * (Math.abs(p1y - p2y) + 1));
            points += nums[index];
            index++;
        }

//        System.out.println("points = " + points);

        random = new Random();
    }

    public int[] pick() {
        int index = random.nextInt(points);
        index++;
        int lenTag = 0;
        for (int i = 0; i < len; i++) {
            if (index > nums[i]) {
                index -= nums[i];
                lenTag++;
                continue;
            }
            break;
        }

        int p1x = rects[lenTag][0];
        int p1y = rects[lenTag][1];
        int p2x = rects[lenTag][2];
        int p2y = rects[lenTag][3];

        int width = Math.abs(p1x - p2x) + 1;
//        int height = Math.abs(p1y - p2y) + 1;

        int resultX;
        int resultY;

        int right = index % width;
        int up = index / width;
        if (right != 0) {
            up++;
            resultX = p1x + right - 1;
            resultY = p1y + up - 1;
        } else {
            resultX = p2x;
            resultY = p1y + up - 1;
        }

        int[] result = new int[]{resultX, resultY};

        return result;
    }
}
